package main.Q801_900;

import java.util.Arrays;
import java.util.Comparator;

public class Q821_830 {
    public static void main(String[] args) {
        System.out.println("Question821：字符的最短距离");
        System.out.println("Question822：");
        System.out.println("Question823：");
        System.out.println("Question824：");
        System.out.println("Question825：");
        System.out.println("Question826：安排工作以达到最大收益");
        System.out.println("Question827：");
        System.out.println("Question828：");
        System.out.println("Question829：");
        System.out.println("Question830：");
    }
}

class Question821{
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] result = new int[n];
        for (int i = 0, idx = -n; i < n; ++i) {
            if (s.charAt(i) == c) idx = i;
            result[i] = i - idx;
        }
        for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
            if (s.charAt(i) == c) idx = i;
            result[i] = Math.min(result[i], idx - i);
        }
        return result;
    }
}

class Question826{
    public int process(int[][] dp,int work){
        int left=0,right= dp.length;
        while (left<right){
            int mid=left+(right-left)/2;
            if (dp[mid][0]>work) right=mid;
            else left=mid+1;
        }
        return right-1;
    }
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int length= difficulty.length,total=0;
        int[][] dp=new int[length][2];
        for (int i=0;i<length;i++){//难度与收益关系并排序
            dp[i][0]=difficulty[i];
            dp[i][1]=profit[i];
        }
        Arrays.sort(dp, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0]!=o2[0]) return o1[0]-o2[0];
                else return o1[1]-o2[1];
            }
        });
        for (int work:worker){
            int index=process(dp,work);//获取当前工人所能完成的最难工作下标
            int maxPro=0;
            if (index>-1){
                for (int i=0;i<=index;i++) maxPro=Math.max(maxPro,dp[i][1]);
            }
            total+=maxPro;
        }
        return total;
    }
}